#include <stdio.h>
#include <stdlib.h>

#define NodeType int
#define ElementType int

typedef struct TreeNode *BinTree;
typedef BinTree Position;

struct TreeNode
{
    NodeType data;
    BinTree left;
    BinTree right;
};
// 二叉搜索树  似乎和二分查找很像？

Position Find(ElementType x, BinTree BT)
{
    if (BT == NULL)
        return NULL;
    if (x == BT->data)
        return BT;
    else if (x < BT->data)
        return Find(x, BT->left);
    else
        return Find(x, BT->right);
}

//二叉搜索树的最大节点和最小节点
Position FindMin(BinTree BT)
{
    if(BT == NULL)
        return NULL;
    else if(BT->left == NULL)
        return BT;
    else
        return FindMin(BT->left);
}

Position FindMax(BinTree BT)
{
    if(BT == NULL)
        return NULL;
    else
    {
        while(BT->right!= NULL)
            BT = BT->right;
    }
    return BT;
}

// 二叉搜索树的插入
Position Insert(ElementType x, BinTree BT)
{ // 这个递归太jb妙了吧
    if (BT == NULL)
    {
        BT = (BinTree)malloc(sizeof(struct TreeNode));
        BT->data = x;
        BT->left = BT->right = NULL;
    }
    else
    {
        if (x < BT->data)
            BT->left = Insert(x, BT->left);
        else if (x > BT->data)
            BT->right = Insert(x, BT->right);
    }
    return BT;
}

// 二叉搜索树的删除
//分类讨论：
//叶节点：直接删除，将父节点的left or right改一下
//只有一个孩子的结点：把孩子挂在父亲的地方
//有两个孩子的结点：用另一结点替代被删除结点：右子树的最小元素or左子树的最大元素---》这些结点都是一定没有两个孩子的结点
Position DeleteTree(ElementType x,BinTree BT)
{
    BinTree temp;
    if(BT == NULL)
        printf("没有找到要删除的元素");
    else
    {
        if(x < BT->data)
            BT->left = DeleteTree(x, BT->left);
        else if(x > BT->data)
            BT->right = DeleteTree(x, BT->right);
        else//找到这个结点了
        {
            if(BT->left != NULL && BT->right != NULL)
            {
                temp = FindMin(BT->right);//右子树的最小结点
                BT->data = temp->data;
                BT->right = DeleteTree(temp->data, BT->right);//删除上述结点
            }
            else//若该结点只有一个孩子或没有孩子
            {
                temp = BT;
                if(BT->left == NULL)
                    BT = BT->right;
                else if(BT->right == NULL)
                    BT = BT->left;
                free(temp);
            }
        }
    }
    return BT;
}